CS 4311-1

Brief

大網： I Foundations 1. The role of Algorithms in Computing 2. Getting Started 3. Growth of Functions 4. Divide-and-Conquer II Sorting and Order Statistics 6. Heapsort 7. Quicksort 8. Sorting in Linear Time 9. Medians and Order Statistics IV Advanced Design and Analysis Techniques 15. Dynamic Programming 16. Greedy Algorithms 17. Amortized Analysis V Advanced Data Structures 21. Data Structures for Disjoint Sets VI Graph Algorithms 22. Elementary Graph Algorithms 23. Minimum Spanning Trees 24. Single-Source Shortest Paths 25. All-Pairs Shortest Paths 26. Maximum Flow VII Selected Topics 31. Number-Theoretic Algorithms 33. Computational Geometry 34. NP-Completeness 35. Approximation Algorithms

Description

Course keywords: algorithms, data structures 一、課程說明(Course Description) 先修：資料結構, 離散樹學 目的：Introduction to Algorithms 大網： I Foundations 1. The role of Algorithms in Computing 2. Getting Started 3. Growth of Functions 4. Divide-and-Conquer II Sorting and Order Statistics 6. Heapsort 7. Quicksort 8. Sorting in Linear Time 9. Medians and Order Statistics IV Advanced Design and Analysis Techniques 15. Dynamic Programming 16. Greedy Algorithms 17. Amortized Analysis V Advanced Data Structures 21. Data Structures for Disjoint Sets VI Graph Algorithms 22. Elementary Graph Algorithms 23. Minimum Spanning Trees 24. Single-Source Shortest Paths 25. All-Pairs Shortest Paths 26. Maximum Flow VII Selected Topics 31. Number-Theoretic Algorithms 33. Computational Geometry 34. NP-Completeness 35. Approximation Algorithms Self-educated: Chapters 10~12, 18, 30, 32 二、指定用書(Text Books) T. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to algorithms, 3rd edition, the MIT press, 2009. 三、參考書籍(References) R. C. T. Lee, R. C. Chang, S. S. Tseng, and Y. T. Tsai, Introduction to the Design and Analysis of Algorithms, 松崗, 1999. 四、教學方式(Teaching Method) 五、教學進度(Syllabus) 六、成績考核(Evaluation) 作業: 20% 期中考：35％ 期末考：45％ 七、可連結之網頁位址 課程中發給

Timetable

PTT Reviews

Remarks

非資工本系生請修習108下特別為資工輔系、雙主修、專長同學開設之同名課程。

Restrictions

資工系大學部3年級優先，第3次選課起開放全校修習

Compulsory

Elective

Cross Discipline

First Specialization

Second Specialization